package leetcode.f1t100;

/**
 * p带*和., s为普通字符串, 返回p是否可以匹配s
 * https://leetcode.com/problems/regular-expression-matching/
 *
 * @author lichx
 * @date 2021/9/27 14:15
 */
public class Q10_RegularExpressionMatching {

    public static void main(String[] args) {
        System.out.println(doProcess("aaaaaaaaaaaaab", "a*a*a*a*a*a*a*a*a*a*a*a*b"));
        System.out.println(doProcess("aaca", "ab*a*c*a"));
        System.out.println(doProcess("aa", "a*"));
        System.out.println(doProcess("bbbbba", ".*a*a"));
        System.out.println(doProcess("mississippi", "mis*is*p*."));
    }

    public static boolean doProcess(String s, String p) {
        char[] c = s.toCharArray();
        char[] m = p.toCharArray();
        int i = 0, j = 0;
        int[][] cache = new int[c.length + 1][m.length + 1];
//        return recursive(c, m, 0, 0);
//        return cache(c, m, 0, 0, cache) == 1;
        return dp(c, m);
//        return process(c,m,0,0);
//        return cache2(c,m,0,0,cache) == 1;
    }

    public static boolean recursive(char[] c, char[] m, int i, int j) {
        if (i == c.length && j == m.length) {
            return true;
        }
        if (i == c.length && j < m.length) {
            if (j + 1 < m.length && m[j + 1] == '*') {
                return recursive(c, m, i, j + 2);
            }
            return false;
        }

        if (i >= c.length || j >= m.length) {
            return false;
        }
        if (j + 1 < m.length && m[j + 1] == '*') {
            if (c[i] == m[j] || m[j] == '.') {
                boolean p1 = recursive(c, m, i + 1, j);
                boolean p2 = recursive(c, m, i + 1, j + 2);
                boolean p3 = recursive(c, m, i, j + 2);
                return p1 || p2 || p3;
            } else {
                return recursive(c, m, i, j + 2);
            }
        } else {
            return c[i] == m[j] || m[j] == '.' ? recursive(c, m, i + 1, j + 1) : false;
        }
    }

    public static int cache(char[] c, char[] m, int i, int j, int[][] cache) {
        if (cache[i][j] != 0) {
            return cache[i][j];
        }
        if (i == c.length && j == m.length) {
            cache[i][j] = 1;
            return cache[i][j];
        }
        if (i == c.length && j < m.length) {
            if (j + 1 < m.length && m[j + 1] == '*') {
                cache[i][j] = cache(c, m, i, j + 2, cache);
                return cache[i][j];
            }
            cache[i][j] = -1;
            return cache[i][j];
        }
        if (i >= c.length || j >= m.length) {
            cache[i][j] = -1;
            return cache[i][j];
        }
        if (j + 1 < m.length && m[j + 1] == '*') {
            if (c[i] == m[j] || m[j] == '.') {
                int p1 = cache(c, m, i + 1, j, cache);
                int p2 = cache(c, m, i + 1, j + 2, cache);
                int p3 = cache(c, m, i, j + 2, cache);
                cache[i][j] = p1 == 1 || p2 == 1 || p3 == 1 ? 1 : -1;
                return cache[i][j];
            } else {
                cache[i][j] = cache(c, m, i, j + 2, cache);
                return cache[i][j];
            }
        } else {
            cache[i][j] = c[i] == m[j] || m[j] == '.' ? cache(c, m, i + 1, j + 1, cache) : -1;
            return cache[i][j];
        }
    }

    public static boolean process(char[] c, char[] m, int i, int j) {
        if (i == c.length && j == m.length) {
            return true;
        }
        if (i < c.length && j < m.length) {
            // 当前位置匹配上了
            if (isMatch(c[i], m[j])) {
                if(j+1<m.length && m[j+1] == '*'){
                    boolean p1 = process(c,m,i+1,j);
                    boolean p2 = process(c,m,i+1,j+2);
                    boolean p3 = process(c,m,i,j+2);
                    return p1 || p2 || p3;
                }
                return process(c, m, i + 1, j + 1);
            }
            // 当前位置没匹配上
            if(j+1<m.length && m[j+1] == '*'){
                return process(c,m,i,j+2);
            }
            return false;
        }
        //原字符串已匹配完成,但表达式未完成
        if (j < m.length - 1 && m[j+1] == '*') {
            return process(c, m, i, j + 2);
        }
        return false;
    }

    public static int cache2(char[] c, char[] m, int i, int j,int[][] cache) {
        if(cache[i][j] != 0){
            return cache[i][j];
        }
        if (i == c.length && j == m.length) {
            cache[i][j] = 1;
            return cache[i][j];
        }
        if (i < c.length && j < m.length) {
            // 当前位置匹配上了
            if (isMatch(c[i], m[j])) {
                if(j+1<m.length && m[j+1] == '*'){
                    int p1 = cache2(c,m,i+1,j,cache);
                    int p2 = cache2(c,m,i+1,j+2,cache);
                    int p3 = cache2(c,m,i,j+2,cache);
                    cache[i][j] = p1 == 1 || p2 ==1 || p3 ==1 ? 1 : -1;
                    return cache[i][j];
                }
                cache[i][j] = cache2(c, m, i + 1, j + 1,cache);
                return cache[i][j];
            }
            // 当前位置没匹配上
            if(j+1<m.length && m[j+1] == '*'){
                cache[i][j] = cache2(c,m,i,j+2,cache);
                return cache[i][j];
            }
            cache[i][j] = -1;
            return cache[i][j];
        }
        //原字符串已匹配完成,但表达式未完成
        if (j < m.length - 1 && m[j+1] == '*') {
            cache[i][j] = cache2(c, m, i, j + 2,cache);
            return cache[i][j];
        }
        cache[i][j] = -1;
        return cache[i][j];
    }

    public static boolean isMatch(char a, char b) {
        return b == '.' || b == a;
    }

    public static boolean dp(char[] c, char[] m) {
        boolean[][] dp = new boolean[c.length+1][m.length+1];
        dp[c.length][m.length] = true;
        for(int j=m.length-1;j>=0;j--){
            if (j < m.length - 1 && m[j+1] == '*') {
                dp[c.length][j] = dp[c.length][j + 2];
            }
        }
        for(int i = c.length-1;i>=0;i--){
            for(int j=m.length-1;j>=0;j--){
                if(isMatch(c[i],m[j])){
                    if(j+1<m.length && m[j+1] == '*'){
                        dp[i][j] = dp[i+1][j] || dp[i+1][j+2] || dp[i][j+2];
                    }else{
                        dp[i][j] = dp[i+1][j+1];
                    }
                }else{
                    if(j+1<m.length && m[j+1] == '*'){
                        dp[i][j] = dp[i][j+2];
                    }
                }
            }
        }
        return dp[0][0];
    }

}
